/*
 *   项目名称：leetcode
 *   文件名称：com.xiaolon.leetcode.Main
 *
 *   创建人：  ZHOU XIAO LONG
 *   创建日期：2024/6/16
 */
package com.xiaolon.leetcode;

import com.xiaolon.leetcode.sort.QuickSortDemo;

import java.util.Arrays;
import java.util.Random;

/**
 * 类描述： Main
 **/
public class Main {

    public static void main(String[] args) {
        int[] arr1 = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
        int[] arr2 = new int[]{9, 2, 7, 2, 5, 2, 3, 2, 1};

        System.out.println("============快速排序================");
        quickSort(arr1, 0, arr1.length-1);
        System.out.println(Arrays.toString(arr1));

        quickSort(arr2, 0, arr2.length-1);
        System.out.println(Arrays.toString(arr2));
//
//        System.out.println("============归并排序================");
//        mergeSort(arr2, 0, arr2.length-1);
//        System.out.println(Arrays.toString(arr2));

    }


    public static void quickSort(int[] nums, int left, int right) {
        if(left < right){
            // 找基准，排左右
            int pivot = partition(nums, left, right);
            quickSort(nums, left, pivot - 1);
            quickSort(nums, pivot + 1, right);
        }
    }

    public static int partition(int[] nums, int left, int right) {
        Random random = new Random();
        int povit = random.nextInt(right - left +1) + left;
        swap(nums, povit, right);

        int slow = left - 1;
        int fast = left;
        while(fast < right){
            if(nums[fast] < nums[right]) swap(nums, ++slow, fast);
            fast++;
        }
        swap(nums, ++slow, right);
        return slow;
    }

    public static void swap(int[] nums, int idx1, int idx2) {
        if(idx1 != idx2){
            int temp = nums[idx1];
            nums[idx1] = nums[idx2];
            nums[idx2] = temp;
        }
    }

//
//    public static void mergeSort(int[] arr, int left, int right){
//        // 拆分+合并
//
//        if(left < right){
//            int mid = (right + left)/2;
//            mergeSort(arr, left, mid);
//            mergeSort(arr, mid+1, right);
//            merge(arr, left, mid, right);
//        }
//
//    }
//    public static void merge(int[] arr, int left, int mid, int right){
//        int[] temp = Arrays.copyOf(arr, arr.length);
//        int p1=left,p2=mid+1,p3=left;
//
//        while(p1<=mid && p2<=right){
//            arr[p3++] = temp[p1] < temp[p2] ? temp[p1++] : temp[p2++];
//        }
//
//        while(p1<left) arr[p3++] = temp[p1++];
//        while(p2<right) arr[p3++] = temp[p2++];
//
//    }
}